#include <bits/stdc++.h>

#define int long long

using namespace std;

void solve()
{
    int n,k;
    cin >> n >> k;
    vector<int> s;
    int cnt = 0;
    while(n)
    {
        s.push_back((n % 3));
        cnt += n % 3;
        n /= 3;
    }
    if(cnt > k)
    {
        cout << "-1" << endl;
        return;
    }
    int lens = s.size() - 1;
    k -= cnt;
    while(k && lens >= 1)
    {
        if(s[lens] * 2 <= k)
        {
            s[lens - 1] += 3 * s[lens];
            k -= s[lens] * 2;
            lens --;
        }
        else
        {
            s[lens] -= k / 2;
            s[lens - 1] += (k / 2) * 3;
            break;
        }
    }
    int ans = 0;
    int judge = 1;
    for(int i = 0; i <= lens; i ++)
    {
        ans += s[i] * (judge * 3 + i * judge / 3);
        judge *= 3;
    } 
    cout << ans << endl;
}

signed main()
{
    int t;
    cin >> t;
    while(t --)
    {
        solve();
    }
}